package com.data.construct.queue;

import java.util.Comparator;
import java.util.NoSuchElementException;

/**
 * 利用二叉堆(数组形式)实现的优先级队列
 * 实现的是小顶堆, 若要实现大顶堆则修改swim和sink方法即可
 * <p>
 * 二叉堆是一种能够动态排序的数据结构，是二叉树结构 的延伸。
 * 二叉堆就是一种能够动态排序的数据结构。
 * 所谓动态排序，就是说我们可以不断往数据结构里面添加或删除元素，数据结构会自动调整元素的位置，
 * 使得我们可以有序地从数据结构中读取元素，这是一般的排序算法做不到的。
 * <p>
 * 你可以认为二叉堆是一种特殊的二叉树，这棵二叉树上的任意节点的值，都必须大于等于（或小于等于）其左右子树所有节点的值。
 * 如果是大于等于，我们称之为「大顶堆」，如果是小于等于，我们称之为「小顶堆」。
 * <p>
 * 对于小顶堆，每个节点下方的所有节点的值都比它大，那么不难想象根节点就是整棵树上的最小值。
 * 同理，大顶堆的根节点就是整棵树上的最大值。所以二叉堆可以辅助我们快速找到最大值或最小值。
 * <p>
 * 二叉堆还有个性质：一个二叉堆的左右子堆（子树）也是一个二叉堆。
 *
 * @author sunhl
 * @Description:
 * @Date: created in 2024/11/18 0018 14:31
 * @Modified By:
 */
public class MyPriorityQueue<T> {
    /**
     * 数组, 作为二叉堆的容器
     */
    private T[] heap;

    private int size;

    private final Comparator<? super T> comparator;

    public MyPriorityQueue(int capacity, Comparator<? super T> comparator) {
        this.heap = (T[]) new Object[capacity];
        this.size = 0;
        this.comparator = comparator;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 父节点的索引
     *
     * @param nodeIndex
     * @return
     */
    private int parent(int nodeIndex) {
        return (nodeIndex - 1) / 2;
    }

    /**
     * 左子节点的索引
     *
     * @param nodeIndex
     * @return
     */
    private int left(int nodeIndex) {
        return nodeIndex * 2 + 1;
    }

    /**
     * 右子节点的索引
     *
     * @param nodeIndex
     * @return
     */
    private int right(int nodeIndex) {
        return nodeIndex * 2 + 2;
    }

    /**
     * 交换数组的两个元素
     *
     * @param i
     * @param j
     */
    private void swap(int i, int j) {
        T temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    /**
     * 上浮操作，时间复杂度是树高 O(logN)
     *
     * @param nodeIndex
     */
    private void swim(int nodeIndex) {
        while (nodeIndex > 0 && comparator.compare(heap[parent(nodeIndex)], heap[nodeIndex]) > 0) {
            swap(parent(nodeIndex), nodeIndex);
            nodeIndex = parent(nodeIndex);
        }
    }

    /**
     * 下沉操作，时间复杂度是树高 O(logN)
     *
     * @param nodeIndex
     */
    private void sink(int nodeIndex) {
        while (left(nodeIndex) < size || right(nodeIndex) < size) {
            // 比较自己和左右子节点，看看谁最小
            int min = nodeIndex;
            if (left(nodeIndex) < size && comparator.compare(heap[left(nodeIndex)], heap[min]) < 0) {
                min = left(nodeIndex);
            }
            if (right(nodeIndex) < size && comparator.compare(heap[right(nodeIndex)], heap[min]) < 0) {
                min = right(nodeIndex);
            }
            if (min == nodeIndex) {
                break;
            }
            swap(nodeIndex, min);
            nodeIndex = min;
        }
    }

    /**
     * 调整堆的大小
     *
     * @param capacity
     */
    @SuppressWarnings("unchecked")
    private void resize(int capacity) {
        assert capacity > size;
        T[] temp = (T[]) new Object[capacity];
        for (int i = 0; i < size; i++) {
            temp[i] = heap[i];
        }
        heap = temp;
    }

    /**
     * 查，返回堆顶元素，时间复杂度 O(1)
     *
     * @return
     */
    public T peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("Priority queue underflow");
        }
        return heap[0];
    }

    /**
     * 增，向堆中插入一个元素，时间复杂度 O(logN)
     *
     * @param x
     */
    public void push(T x) {
        // 扩容
        if (size == heap.length) {
            resize(2 * heap.length);
        }
        // 把新元素追加到最后
        heap[size] = x;
        // 然后上浮到正确位置
        swim(size);
        size++;
    }

    /**
     * 删，删除堆顶元素，时间复杂度 O(logN)
     *
     * @return
     */
    public T pop() {
        if (isEmpty()) {
            throw new NoSuchElementException("Priority queue underflow");
        }
        T res = heap[0];
        // 把堆底元素放到堆顶
        swap(0, size - 1);
        // 避免对象游离
        heap[size - 1] = null;
        size--;
        // 然后下沉到正确位置
        sink(0);
        // 缩容
        if ((size > 0) && (size == heap.length / 4)) {
            resize(heap.length / 2);
        }
        return res;
    }

    public static void main(String[] args) {
        MyPriorityQueue<Integer> pq = new MyPriorityQueue<>(3, Comparator.naturalOrder());
        pq.push(3);
        pq.push(1);
        pq.push(4);
        pq.push(1);
        pq.push(5);
        pq.push(9);
        // 1 1 3 4 5 9
        while (!pq.isEmpty()) {
            System.out.println(pq.pop());
        }
    }
}
